package dichotomy.pow.x.y;
/**
 * @Time 2020/1/20
 * @author 王光浩
 * @Need 给出x和y求出x^y的值。y的取值范围为[-2^31,2^31-1]
 * @Thinking 使用快速幂的递归方法。
 *           复杂度分析：时间复杂度O（logn），空间复杂度O（1）
 */
	public class OtherMethodOne {
	    public double myPow(double x, int n) {
	    	if(x==0 || x==1 || n==1)return x;
	    	if(n==0)return 1;
	    	int absn=(n==Integer.MIN_VALUE?Integer.MAX_VALUE:Math.abs(n));
	    	double res=fastPow(x,absn);
	    	if(n==Integer.MIN_VALUE)res*=x;
	    	return n<0?1/res:res;
	    }
		//当n为偶数时，x^n=x^(n/2)*x^(n/2)，当x为奇数时x^n=x^(n/2)*x^(n/2)*x
	    private double fastPow(double x,int n) {
	    	if(n==0)//递归结束条件
	    		return 1.0;
	    	double half=fastPow(x,n/2);
	    	if(n%2==0)
	    		return half*half;
	    	else
	    		return half*half*x;
	    }
}
